/*-------------------------------------------------------------------------
 *
 * bitmapset.h
 *	  PostgreSQL通用位图集包
 *
 * 位图集可以表示任何非负整数的集合，尽管它主要用于最大值不大的集合，
 * 比如最多几百。根据约定，所有操作都始终接受一个NULL指针以表示空集合。
 * （但注意，这不是空集合的唯一表示。最好使用bms_is_empty()而不是测试NULL。）
 *
 *
 * Copyright (c) 2003-2022, PostgreSQL Global Development Group
 *
 * src/include/nodes/bitmapset.h
 *
 *-------------------------------------------------------------------------
 */
#ifndef BITMAPSET_H
#define BITMAPSET_H

/*
 * 前向声明以避免包含pg_list.h
 */
struct List;

/*
 * 数据表示
 *
 * 较大的位图字大小通常能提供更好的性能，只要
 * 它们不宽于处理器能够高效处理的范围。我们使用
 * 64位字，如果指针足够大，否则使用32位字。
 */
#if SIZEOF_VOID_P >= 8

#define BITS_PER_BITMAPWORD 64
typedef uint64 bitmapword;		/* 必须是无符号类型 */
typedef int64 signedbitmapword; /* 必须是匹配的有符号类型 */

#else

#define BITS_PER_BITMAPWORD 32
typedef uint32 bitmapword;		/* 必须是无符号类型 */
typedef int32 signedbitmapword; /* 必须是匹配的有符号类型 */

#endif

typedef struct Bitmapset
{
	int			nwords;			/* 数组中的字数 */
	bitmapword	words[FLEXIBLE_ARRAY_MEMBER];	/* 实际上是[nwords] */
} Bitmapset;


/* bms_subset_compare的结果 */
typedef enum
{
	BMS_EQUAL,					/* 集合相等 */
	BMS_SUBSET1,				/* 第一个集合是第二个集合的子集 */
	BMS_SUBSET2,				/* 第二个集合是第一个集合的子集 */
	BMS_DIFFERENT				/* 两个集合都不是彼此的子集 */
} BMS_Comparison;

/* bms_membership 的结果 */
typedef enum
{
	BMS_EMPTY_SET,				/* 0 个成员 */
	BMS_SINGLETON,				/* 1 member */
	BMS_MULTIPLE				/* >1 个成员 */
} BMS_Membership;


/*
 * nodes/bitmapset.c 中的函数原型
 */

extern Bitmapset *bms_copy(const Bitmapset *a);
extern bool bms_equal(const Bitmapset *a, const Bitmapset *b);
extern int	bms_compare(const Bitmapset *a, const Bitmapset *b);
extern Bitmapset *bms_make_singleton(int x);
extern void bms_free(Bitmapset *a);

extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b);
extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);
extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
extern BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b);
extern bool bms_is_member(int x, const Bitmapset *a);
extern int	bms_member_index(Bitmapset *a, int x);
extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
extern bool bms_overlap_list(const Bitmapset *a, const struct List *b);
extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
extern int	bms_singleton_member(const Bitmapset *a);
extern bool bms_get_singleton_member(const Bitmapset *a, int *member);
extern int	bms_num_members(const Bitmapset *a);

/* 当我们不需要确切的成员计数时的优化测试： */
extern BMS_Membership bms_membership(const Bitmapset *a);
extern bool bms_is_empty(const Bitmapset *a);

/* 这些例程循环使用（修改或释放）它们的非 const 输入： */

extern Bitmapset *bms_add_member(Bitmapset *a, int x);
extern Bitmapset *bms_del_member(Bitmapset *a, int x);
extern Bitmapset *bms_add_members(Bitmapset *a, const Bitmapset *b);
extern Bitmapset *bms_add_range(Bitmapset *a, int lower, int upper);
extern Bitmapset *bms_int_members(Bitmapset *a, const Bitmapset *b);
extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b);
extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b);

/* 支持迭代集合的整数元素： */
extern int	bms_first_member(Bitmapset *a);
extern int	bms_next_member(const Bitmapset *a, int prevbit);
extern int	bms_prev_member(const Bitmapset *a, int prevbit);

/* 支持使用 Bitmapsets 作为键的哈希表： */
extern uint32 bms_hash_value(const Bitmapset *a);
extern uint32 bitmap_hash(const void *key, Size keysize);
extern int	bitmap_match(const void *key1, const void *key2, Size keysize);

#endif							/* BITMAPSET_H */
